//136. 只出现一次的数字
//给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
//你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

//https://leetcode.cn/problems/single-number/description/?orderBy=most_votes

//hashmap 
int singleNumber(int* nums, int numsSize)
{
    if (numsSize == 1)
    {
        return *nums;
    }
    //开空间
    int max = *nums;
    int min = *nums;
    for (int i = 0; i < numsSize; i++)
    {
        if (max < *(nums + i))
        {
            max = *(nums + i);
        }
        if (min > *(nums + i))
        {
            min = *(nums + i);
        }
    }
    int* tmp = (int*)malloc(sizeof(int) * (max - min+1));
    memset(tmp, 0, sizeof(int) * (max - min+1));
    //放入数据
    for (int i = 0; i < numsSize; i++)
    {
        tmp[nums[i] - min] += 1;
    }
    for (int i = 0; i < (max - min+1); i++)
    {
        if (*(tmp + i) == 1)
        {
            return i + min;
        }
    }
    free(tmp);
    tmp=NULL;
    return 0;
}


//位运算
int singleNumber(int* nums, int numsSize)
{
    int tmp=*nums;
    if(numsSize>1)
    {
        for(int i=1;i<numsSize;i++)
        {
            tmp=tmp^*(nums+i);
        }
    }
    return tmp;

}